package leetcode.problems;

import org.junit.Test;

/**
 * Created by gmwang on 2018/7/25
 * 最长的不常见子序列
 */
public class _0824LongestUncommonSubsequenceI {
    /**
     *
     * Given a group of two strings, you need to find the longest uncommon subsequence of this group of two strings.
     * 给定一组两个字符串，则需要找到该组两个字符串中最长的不常见子序列。
     *
     * The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings.
     * 最长的不常见子序列被定义为这些字符串之一的最长的子序列,并且这个子序列不应该是其他字符串的任何子序列。
     *
     * A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements.
     * 子序列是通过删除一些字符而不改变其余元素的顺序而从一个序列导出的序列
     *
     * Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.
     * 任何字符串都是自己的子序列，空字符串是任何字符串的子序列。
     *
     * The input will be two strings, and the output needs to be the length of the longest uncommon subsequence.
     * 输入将是两个字符串，输出需要是最长的不寻常子序列的长度。
     *
     * If the longest uncommon subsequence doesn't exist, return -1.
     * 如果最长的不常见子序列不存在，返回- 1。
     * Example 1:
     * Input: "aba", "cdc"
     * Output: 3
     * Explanation: The longest uncommon subsequence is "aba" (or "cdc"),
     * because "aba" is a subsequence of "aba",
     * but not a subsequence of any other strings in the group of two strings.
     * Note:
     *
     * Both strings' lengths will not exceed 100.
     * Only letters from a ~ z will appear in input strings.
    /**
     *
     * @param a,b
     * @return
     */
    public int findLUSlength(String a, String b) {
        char[] a1 = a.toCharArray();
        char[] a2 = b.toCharArray();
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        for (int i = 0; i < a1.length; i++) {
            String s1 =sb1.toString()+a1[i];
            if(!b.contains(s1)){
                sb1.append(a1[i]);
            }else{
                if(sb1.length() > 1){
                   sb1.substring(1);
                }else {
                    if(i == 0){
                        sb1.append(a2[i]);
                    }else if(sb1.length() == 1){
                        sb1 = new StringBuilder();
                    }
                }
            }
        }
        for (int i = 0; i < a2.length; i++) {
            String s2 =sb2.toString()+a2[i];
            if(!a.contains(s2) ){
                sb2.append(a2[i]);
            }else{
                if(sb2.length() > 1){
                    sb2.substring(1);
                }else {
                    if(i == 0){
                        sb2.append(a2[i]);
                    }else if(sb2.length() == 1){
                        sb2 = new StringBuilder();
                    }
                }
            }
        }
        if(sb1.length() == 0 && sb2.length() == 0 && a.length() == b.length()) return -1;
        if(a.length() != b.length()) return Math.max(a.length(),b.length());
        return Math.max(sb1.length(),sb2.length());
    }
//    public int findLUSlength(String a, String b) {
//        if(a.length() == b.length()){
//            if(a == b){
//                return  -1;
//            }
//            return a.length();
//        }else {
//            return Math.max(a.length(),b.length());
//        }
//    }
    @Test
    public void test() {
//        String a = "aba";
//        String b =  "cdc";
//        String a = "aaa";   // -1
//        String b =  "aaa";
//        String a = "aefawfawfawfaw";
//        String b =  "aefawfeawfwafwaef";  //17

        String a = "horbxeemlgqpqbujbdagizcfairalg";
        String b = "iwvtgyojrfhyzgyzeikqagpfjoaeen";  //30
        int res = findLUSlength(a,b);
        System.out.println(res);
    }
}
